package coc.core.filter;

import coo.base.util.StringUtils;

/**
 * 布隆过滤器基类。
 */
public abstract class BloomFilter {
	/** bit位的数量 */
	protected Integer bitSetSize;
	/** 计算使用哈希函数的个数 */
	protected Integer hashCount;

	/**
	 * 构造方法。
	 * 
	 * @param collisionRate
	 *            允许碰撞率
	 * @param elementCount
	 *            期望放入元素数量
	 */
	public BloomFilter(Double collisionRate, Integer elementCount) {
		Double perElementBitSize = Math.ceil(-(Math.log(collisionRate) / Math
				.log(2))) / Math.log(2);
		this.hashCount = (int) Math.ceil(-(Math.log(collisionRate) / Math
				.log(2)));
		this.bitSetSize = (int) Math.ceil(perElementBitSize * elementCount);
	}

	/**
	 * 增加字符串。
	 * 
	 * @param str
	 *            待增加的字符串
	 */
	public void add(String str) {
		for (int i : createHashs(str)) {
			setBit(i, true);
		}
	}

	/**
	 * 判断字符串是否已存在。
	 * 
	 * @param str
	 *            待判断的字符串
	 * @return 如果存在返回true，否则返回false。
	 */
	public boolean contains(String str) {
		if (StringUtils.isBlank(str)) {
			return false;
		}
		for (int i : createHashs(str)) {
			if (!getBit(i)) {
				return false;
			}
		}
		return true;
	}

	/**
	 * 生成指定字符串的hash数组。
	 * 
	 * @param str
	 *            待哈希计算的字符串
	 * @return 返回生成的hash数组。
	 */
	private int[] createHashs(String str) {
		int[] result = new int[hashCount];
		byte[] bytes = str.getBytes();
		int hash1 = MurmurHash.hash32(bytes, bytes.length, 0);
		int hash2 = MurmurHash.hash32(bytes, bytes.length, hash1);
		for (int i = 0; i < hashCount; ++i) {
			result[i] = (Math.abs((hash1 + i * hash2) % bitSetSize));
		}
		return result;
	}

	/**
	 * 获取指定位置bit的值。
	 * 
	 * @param offset
	 *            位置偏移值
	 * @return 如果bit值为1则返回true，否则返回false。
	 */
	protected abstract Boolean getBit(Integer offset);

	/**
	 * 设置指定位置bit的值。
	 * 
	 * @param offset
	 *            位置偏移值
	 * @param value
	 *            待设置的值
	 */
	protected abstract void setBit(Integer offset, Boolean value);
}
